class Solution
{
public:
    int numTilePossibilities(string tiles)
    {
        unordered_set<string> combinations;
        select(tiles, 0, "", combinations);
        combinations.erase("");
        vector<string> permutations;
        for (string tileComb : combinations)
        {
            perm(tileComb, 0, permutations);
        }
        return permutations.size();
    }

    void select(string &s, int curId, string cur, unordered_set<string> &result)
    {
        if (curId == s.size())
        {
            sort(cur.begin(), cur.end());
            result.insert(cur);
            return;
        }
        select(s, curId + 1, cur, result);
        cur += s[curId];
        select(s, curId + 1, cur, result);
    }

    void perm(string &s, int cur, vector<string> &result)
    {
        if (cur == s.size())
        {
            result.push_back(s);
            return;
        }
        unordered_set<char> occurred;
        for (int i = cur; i < s.size(); ++i)
        {
            if (!occurred.count(s[i]))
            {
                swap(s[cur], s[i]);
                occurred.insert(s[cur]);
                perm(s, cur + 1, result);
                swap(s[cur], s[i]);
            }
        }
    }
};